The present invention relates generally to a negotiation mechanism, and more particularly, to a method and apparatus for negotiating performance of a set of actions by a plurality of participants in the negotiation.
Negotiation is a pervasive aspect of everyday life, and it is not surprising that various approaches have been proposed to use computer software to support some forms of negotiation processes in various applications. In particular, existing multi-agent systems support negotiations in meeting scheduling, electronic trading, service matching and many other collaborative applications. More generic forms of negotiation also exist in service discovery mechanisms, advanced transaction models, quality of service selection etc.
While most of these forms of negotiation make sense in the context of the applications for which they have been designed, they are difficult to transport across applications, and across architectural layers within an application. In other words, there is no satisfactory generic model of negotiation that could provide the basis of a middleware tool that any distributed application could rely on at multiple levels.
Middleware systems are programs that provide “glue” for programmatically coupling various components of a distributed program. Such systems are gaining momentum, following the extensive use of the Internet and intranets, because they try to address recurrent needs of distributed application development, such as in the domain of electronic commerce. In addition, middleware is evolving towards the role of an “integration tool” for coordinating users and applications.
One example of a middleware system is CLF (Coordination Language Facility) developed by Xerox Corporation. CLF is a lightweight coordination middleware toolkit designed to integrate discovery, transaction and notification aspects in distributed component systems. Aspects of CLF are described by: J-M. Andreoli et al., in “Multiparty Negotiation for Dynamic Distributed Object Services”, published in Journal of Science of Computer Programming, 31(2-3):179-203, 1998; J-M. Andreoli et al., in “CLF/Mekano: a Framework for Building Virtual-Enterprise Applications”, published in Proc. of EDOC'99, Manheim, Germany, 1999; and J-M. Andreoli and S. Castellani, in “Towards a Flexible Middleware Negotiation Facility for Distributed Components”, published in Proc. of DEXA 2000 e-Negotiations Workshop, Munich, Germany, 2001.
While existing middleware systems currently provide some form of support for network communication, coordination, reliability, scalability, and heterogeneity, they however currently: do not scale well beyond local area networks, are not adapted to new forms of networking (e.g. wireless or hybrid), and are not always dependable nor flexible enough to provide generic negotiation capabilities. Some improvements provide large scale distribution, adaptive reconfigurability and support for mobility as described by W. Emmerich, entitled “Software Engineering and Middleware: A Roadmap”, published in Proc. of ICSE 2000, The future of Software Engineering, Munich, Germany, 2001.
Most computing models, however, are not able to support the processing of partial and contextual information, which are important ingredients of negotiation. Indeed, a negotiation decision is always taken in the context of previous decisions that limit its scope of validity, and each decision brings only a partial contribution to the final agreement. In the computing models adopted by most middleware systems (e.g., CLF), it is up to the application programmer to manage partial and contextual information (i.e., to treat two separate values as partial information about the same negotiation, and to keep track of the context of all the decisions that have been made to reach a certain value in a negotiation).
There exists, however, one paradigm that naturally supports both partial and contextual information: constraint programming, and in particular, its (concurrent) logic-programming flavor. In constraint programming, a constraint is a piece of partial information about some entities, and constraints can be gathered into constraint stores which may be non-deterministically and incrementally evolving (typically in a search procedure), each state of the store providing the context for further constraint propagations.
Based on constraint programming concepts, it would be advantageous to provide a new, generic model of negotiation that is independent of any application domain, thus qualifying as foundation for a middleware service, but that also avoids overgeneralization where a negotiation is viewed as any process performing transitions through a state graph, triggered by external actions.